
#include "../include/question.h"

using namespace std;

int Solution_28::strStr(string haystack, string needle) {
    vector<int> next;
    genNext(needle, next);

    int index_source = 0, index_target = 0;
    while (index_source < haystack.size()) {
        if (haystack[index_source] == needle[index_target]) {
            index_source++;
            index_target++;
            if (index_target == needle.size())
                return index_source - index_target;
            continue;
        }
        while (index_target > 0 && haystack[index_source] != needle[index_target]) {
            index_target = next[index_target - 1];
        }
        if (haystack[index_source] == needle[index_target]) {
            index_target++;
        }
        index_source++;
    }

    return -1;
}

void Solution_28::genNext(const string &str, vector<int> &next) {
    next.resize(str.size());
    next[0] = 0;
    for (int i = 1; i < str.size(); i++) {
        int cur = next[i - 1];
        while (cur > 0 && str[i] != str[cur]) {
            cur = next[cur - 1];
        }
        if (str[i] == str[cur]) cur++;
        next[i] = cur;
    }
}

bool Solution_No1::findInt(const std::vector<std::vector<int>>& origin_data, const int target_int) {

    int x{static_cast<int>(origin_data.front().size()) - 1},
        y{static_cast<int>(origin_data.size()) - 1};

    int i{x}, j{0};

    while (i >= 0 && j < y) {
        if (origin_data[i][j] > target_int) {
            i--;
            continue;
        }
        if (origin_data[i][j] < target_int) {
            j++;
            continue;
        }
        return true;
    }
    return false;
}

std::string Solution_No2::replaceSpace(std::string &origin_data) {
    size_t origin_length = origin_data.length();
    size_t space_count = 0;
    for (const auto &ch : origin_data) {
        if (ch == ' ') {
            ++space_count;
        }
    }
    if (space_count == 0) {
        return origin_data;
    }
    size_t new_length = origin_length + space_count * 2;
    origin_data.resize(new_length);
    size_t i_front = new_length;
    {
        int i = static_cast<int>(origin_length);
        for (; i >= 0; --i) {
            if (origin_data[i] != ' ') {
                origin_data[i_front] = origin_data[i];
                i_front--;
            } else {
                origin_data[i_front] = '0';
                origin_data[i_front - 1] = '2';
                origin_data[i_front - 2] = '%';
                i_front -= 3;
            }
        }
    }

    return origin_data;
}

std::vector<int> Solution_No3::printListFromTailToHead(ListNode* head) {
    std::vector<int> result{};
    while (head != nullptr) {
        result.push_back(head->val);
        head = head->next;
    }
    reverse(result.begin(), result.end());
    return result;
}


static TreeNode* recursiveBuildTree(const std::vector<int> &preOrder, int &cur_index, int left_border, int right_border,
                                    const std::vector<int> &vinOrder) {
    std::cout << cur_index << " " << left_border << " " << right_border << "\n";
    if (left_border >= right_border) {
        return nullptr;
    }

    int mid{-1};
    for (int i = left_border; i < right_border; i++) {
        if (preOrder[cur_index] == vinOrder[i]) {
            mid = i;
        }
    }
    if (mid == -1) {
        return nullptr;
    }
    std::cout << mid << "\n";
    auto cur_node = new TreeNode(preOrder[cur_index]);
    ++cur_index;
    cur_node->left = recursiveBuildTree(preOrder, cur_index, left_border, mid, vinOrder);
    cur_node->right = recursiveBuildTree(preOrder, cur_index, mid + 1, right_border, vinOrder);

    return cur_node;
}

TreeNode* Solution_No4::reConstructBinaryTree(const std::vector<int> &preOrder, const std::vector<int> &vinOrder) {
    int cur_index = 0;
    return recursiveBuildTree(preOrder, cur_index, 0, static_cast<int>(vinOrder.size()), vinOrder);
}

void Solution_No5::push(int node) {
    stack1.push(node);
}

int Solution_No5::pop() {
    if (stack2.empty()) {
        while (!stack1.empty()) {
            int val = stack1.top();
            stack1.pop();
            stack2.push(val);
        }
    }
    if (stack2.empty()) {
        return -1;
    } else {
        int val = stack2.top();
        stack2.pop();
        return val;
    }
}

static int binarySearchMin(const std::vector<int> &nums, const int begin,
                           const int end) {
    if (begin == end) {
        return nums[begin];
    }
    if (nums[begin] < nums[end]) {
        return nums[begin];
    }
    int mid = (begin + end) / 2;
    if (nums[mid] > nums[begin]) {
        return binarySearchMin(nums, mid + 1, end);
    } else if (nums[mid] < nums[begin]) {
        return binarySearchMin(nums, begin, mid);
    } else {
        return std::min(binarySearchMin(nums, begin, mid), binarySearchMin(nums, mid + 1, end));
    }
}

int Solution_No6::minNumberInRotateArray(const std::vector<int> &nums) {
    return binarySearchMin(nums, 0, static_cast<int>(nums.size()) - 1);
}

int Solution_No7::Fibonacci(int n) {
    if (n == 1 || n == 2) return 1;
    if (n % 2 != 0) {
        int F1 = Fibonacci(n / 2 + 1), F2 = Fibonacci(n / 2);
        return F1 * F1 + F2 * F2;
    } else {
        int F1 = Fibonacci(n / 2 + 1), F2 = Fibonacci(n / 2), F3 = Fibonacci(n / 2 - 1);
        return F1 * F2 + F2 * F3;
    }
}

int Solution_No8::jumpFloor(int number) {
    return Solution_No7::Fibonacci(number + 1);
}

int Solution_No9::jumpFloorII(int number) {
    return static_cast<int>(std::pow(2, number - 1));
}

int Solution_No10::rectCover(int number) {
    return Solution_No7::Fibonacci(number + 1);
}

int Solution_No11::NumberOf1(int n) {
    int count = 0;
    while (n != 0) {
        count++;
        n = n & (n - 1);
    }
    return count;
}

double Solution_No12::power(double base, int exponent) {
    if (base == 0) return 0.0;
    if (exponent == 0) return 1.0;

    double result = 1;
    double power_value = base;
    bool is_exponent_minus = false;
    if (exponent < 0) {
        is_exponent_minus = true;
        exponent = exponent * (-1);
    }

    while (exponent != 0) {
        if ((exponent & 1) == 1) {
            result = result * power_value;
        }
        power_value *= power_value;
        exponent = exponent >> 1;
    }
    return is_exponent_minus ? 1 / result : result;
}

std::vector<int> Solution_No13::reOrderArray(std::vector<int> &array) {
    size_t front_ptr{0}, back_ptr{0};
    while (front_ptr < array.size() - 1) {
        if ((array[front_ptr] & 1) == 1) {
            front_ptr++;
            continue;
        }
        // 找到了偶数 array[front_ptr]
        back_ptr = front_ptr + 1;
        while (back_ptr < array.size()) {
            if ((array[back_ptr] & 1) == 0) {
                back_ptr++;
                continue;
            }
            break;
        }
        if (back_ptr == array.size()) {
            break;
        }
        // 找到了奇数 array[back_ptr]
        while (back_ptr > front_ptr) {
            std::swap(array[back_ptr], array[back_ptr - 1]);
            back_ptr--;
        }
    }
    return array;
}

int Solution_No14::findKthToTail(ListNode* pListHead, unsigned int k) {
    ListNode* tail_ptr = pListHead;
    ListNode* target_ptr = pListHead;
    while (k > 0) {
        if (tail_ptr == nullptr) {
            return -1;
        }
        k--;
        tail_ptr = tail_ptr->next;
    }
    while (tail_ptr != nullptr) {
        tail_ptr = tail_ptr->next;
        target_ptr = target_ptr->next;
    }
    return target_ptr->val;
}

ListNode* Solution_No15::ReverseList(ListNode* head) {
    if (head == nullptr) {
        return head;
    }
    // init
    auto headNode_ptr = new ListNode(-1);
    headNode_ptr->next = head;
    ListNode* prev_ptr = headNode_ptr->next;
    ListNode* cur_ptr = prev_ptr->next;

    // reverse
    while (cur_ptr != nullptr) {
        ListNode* next_ptr = cur_ptr->next;

        cur_ptr->next = prev_ptr;
        prev_ptr = cur_ptr;
        cur_ptr = next_ptr;
    }
    headNode_ptr->next->next = nullptr;
    headNode_ptr->next = prev_ptr;
    ListNode* result = headNode_ptr->next;

    delete headNode_ptr;
    return result;
}

ListNode* Solution_No15::ReverseList_2(ListNode* head) {
    if (head == nullptr) {
        return head;
    }

    ListNode* prev_ptr = nullptr;
    ListNode* cur_ptr = head;
    ListNode* next_ptr = head->next;
    while (cur_ptr != nullptr) {
        cur_ptr->next = prev_ptr;
        prev_ptr = cur_ptr;
        cur_ptr = next_ptr;
        if (next_ptr) {
            next_ptr = next_ptr->next;
        }
    }
    return prev_ptr;
}

ListNode* Solution_No16::Merge(ListNode* pHead1, ListNode* pHead2) {
    if (pHead1 == nullptr) {
        return pHead2;
    }
    if (pHead2 == nullptr) {
        return pHead1;
    }

    auto mHead = ListNode(-1);
    auto mHead_ptr = &mHead;

    ListNode* cur_ptr = mHead_ptr;
    while(pHead1 && pHead2) {
        if (pHead1->val < pHead2->val) {
            // pHead1
            cur_ptr->next = pHead1;
            cur_ptr = pHead1;
            pHead1 = pHead1->next;
        } else {
            // pHead2
            cur_ptr->next = pHead2;
            cur_ptr = pHead2;
            pHead2 = pHead2->next;
        }
    }
    cur_ptr->next = pHead1 ? pHead1 : pHead2;
    return mHead_ptr->next;
}

static bool has_subTree(TreeNode* pRoot1, TreeNode* pRoot2) {
    if (pRoot2 == nullptr) {
        return true;
    }
    if (pRoot1 == nullptr) {
        return false;
    }

    if (pRoot1->val == pRoot2->val) {
        return has_subTree(pRoot1->left, pRoot2->left) &&
                      has_subTree(pRoot1->right, pRoot2->right);
    }
    return has_subTree(pRoot1->left, pRoot2) ||
           has_subTree(pRoot1->right, pRoot2);
}

bool Solution_No17::HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
    if (pRoot2 == nullptr || pRoot1 == nullptr) {
        return false;
    }
    return has_subTree(pRoot1, pRoot2);
}

static void mirror(TreeNode* pRoot) {
    if (pRoot == nullptr) {
        return ;
    }
    std::swap(pRoot->left, pRoot->right);
    mirror(pRoot->left);
    mirror(pRoot->right);
}

TreeNode* Solution_No18::Mirror(TreeNode* pRoot) {
    if (pRoot == nullptr) {
        return nullptr;
    }
    mirror(pRoot);
    return pRoot;
}

std::vector<int> Solution_No19::printMatrix(std::vector<std::vector<int>> matrix) {

    std::vector<int> result{};

    int length = static_cast<int>(matrix.front().size());
    int weight = static_cast<int>(matrix.size());
    int x = 0, y = 0;
    while (length > 0 && weight > 0) {
        // go right
        for (int count = 0; count < length; count++) {
            result.push_back(matrix[y][x]);
            x++;
        }
        x--;
        y++;
        weight--;
        if (weight == 0) break;

        // go down
        for (int count = 0; count < weight; count++) {
            result.push_back(matrix[y][x]);
            y++;
        }
        y--;
        x--;
        length--;
        if (length == 0) break;

        // go left
        for (int count = 0; count < length; count++) {
            result.push_back(matrix[y][x]);
            x--;
        }
        x++;
        y--;
        weight--;
        if (weight == 0) break;

        // go up
        for (int count = 0; count < weight; count++) {
            result.push_back(matrix[y][x]);
            y--;
        }
        y++;
        x++;
        length--;
        if (length == 0) break;

    }

    return result;
}

int Solution_No20::min() {
    std::shared_ptr<Solution_No20> tmp_stack = std::make_shared<Solution_No20>();
    int min = 10000;
    while (!this->empty()) {
        int val = this->top();
        min =  val  < min ? val : min;
        this->pop();
        tmp_stack->push(val);
    }
    while (!tmp_stack->empty()) {
        this->push(tmp_stack->top());
        tmp_stack->pop();
    }
    return min;
}

void Solution_No20::push(int value) {
    data.push_back(value);
}

int Solution_No20::top() {
    return data.back();
}

void Solution_No20::pop() {
    data.pop_back();
};

bool Solution_No20::empty() {
    return data.empty();
}

bool Solution_No21::IsPopOrder(std::vector<int> &pushV, std::vector<int> &popV) {
    std::stack<int> num_stack{};
    int pop_index = 0;
    for (int num_to_push : pushV) {
        num_stack.push(num_to_push);
        while (!num_stack.empty() && popV[pop_index] == num_stack.top()) {
            num_stack.pop();
            pop_index++;
        }
    }
    if (num_stack.empty()) {
        return true;
    }
    return false;
}

std::vector<int> Solution_No22::PrintFromTopToBottom(TreeNode* root) {
    std::vector<int> result{};

    if (root == nullptr) {
        return result;
    }

    std::queue<TreeNode *> node_queue{};
    node_queue.push(root);
    while (!node_queue.empty()) {
        for (size_t cur_node_count = node_queue.size(); cur_node_count > 0; --cur_node_count) {
            TreeNode* cur_node = node_queue.front();
            node_queue.pop();

            result.push_back(cur_node->val);
            if (cur_node->left) {
                node_queue.push(cur_node->left);
            }
            if (cur_node->right) {
                node_queue.push(cur_node->right);
            }
        }
    }
    return result;
}

bool checkSequence(const std::vector<int> &sequence, int start, int end, int max, int min) {
    if (start == end) {
        return true;
    }
    int cur_val = sequence[start];
    if (cur_val > max || cur_val < min) {
        return false;
    }

    int index = start;
    for (; index < sequence.size(); ++index) {
        if (sequence[index] < cur_val) {
            break;
        }
    }
    return checkSequence(sequence, start + 1, index, )


}

bool Solution_No23::VerifySequenceOfBST(std::vector<int> &sequence) {
    int max = INT32_MAX;
    int min = INT32_MIN;
    reverse(sequence.begin(), sequence.end());

    return checkSequence(sequence, 0, static_cast<int>(sequence.size()), max, min);


}



